package com.jojo.intermediate.day6_string;

import java.util.HashMap;
import java.util.Map;

/**
 * 409、最长回文串
 *
 * 给定一个包含大写字母和小写字母的字符串s，返回通过这些字母构造成的 最长的回文串。
 * 在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。
 *
 * 示例 1:
 * 输入:s = "abccccdd"
 * 输出:7
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 *
 * 示例 2:
 * 输入:s = "a"
 * 输出:1
 *
 * 示例 3：
 * 输入:s = "aaaaaccc"
 * 输出:7
 */
public class LongestPandString {

    /** myCode 哈希表 */
    public int longestPalindrome(String s) {
        if (s.length() == 0){
            return 0;
        }
        char[] chars = s.toCharArray();
        int count = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (char aChar : chars) {
            if(map.containsKey(aChar)){
                map.put(aChar,map.get(aChar) + 1);
                if (map.get(aChar) == 2){
                    count += 2;
                    map.put(aChar,0);
                }
            }else {
                map.put(aChar,1);
            }
        }
        return Math.min(count + 1,s.length());
    }

    /** pe.贪心算法 */
    public int longestPalindrome2(String s) {
        int[] count = new int[128];
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            char c = s.charAt(i);
            count[c]++;
        }

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        LongestPandString pand = new LongestPandString();
        String s = "abccccdd";
        System.out.println(pand.longestPalindrome(s));
    }
}
